/*
 * Università degli Studi di Trento
 * Facoltà di Scienze MM.FF.NN.
 * Corso di Laurea Triennale in Informatica
 * A.A. 2010/2011
 * Progetto per il corso di Sistemi Operativi 1
 * Progetto 4: simulazione di una rotonda
 * Autori:
 *  Abram Lorenzo - 140368
 *  Dal Lago Loris - 139428
 *  Florio Alessandro - 140245
 */

/********************************************************************************
 La coda con priorita' viene implementata tramite uno heap binario capace di
 ridimensionarsi dinamicamente ove necessario, ossia raddoppia di dimensione
 quando il vettore raggiunge la capacita' massima e si dimezza quando la
 dimensione del vettore e' a un quarto della capacita'.

 Questa implementazione specializza la coda per il tipo ptrCar e utilizza un
 mutex per evitare eventuali problemi di concorrenza sulle operazioni di
 enqueue e dequeue
 ********************************************************************************/

#include "priorityQueue.h"

#define MIN_CAPACITY 64

static pthread_mutex_t PQmutex;

typedef struct SPQueue {
	int capacity;
	int size; /* elementi contenuti, sentinella esclusa  */
	ptrCar* carHeap; /* l'array heap */
} PQueue;

bool PQueue_isEmpty(ptrPQueue pqueue) {
	return pqueue->size == 0;
}

static bool PQueue_isEmptyEnough(ptrPQueue pqueue) {
	return (pqueue->size < pqueue->capacity / 4) && (pqueue->capacity
			> MIN_CAPACITY);
}

static bool PQueue_isFull(ptrPQueue pqueue) {
	return pqueue->size == pqueue->capacity;
}

static void PQueue_init(ptrPQueue pqueue) {
	pqueue->capacity = MIN_CAPACITY;
	pqueue->size = 0;
	pqueue->carHeap = new_vector(ptrCar, MIN_CAPACITY+1);
	pqueue->carHeap[0] = NULL; /* sentinella */
	pthread_mutex_init(&PQmutex, NULL);
}

ptrPQueue PQueue_create() {
	ptrPQueue pqueue = new(PQueue);
	PQueue_init(pqueue);
	return pqueue;
}

void PQueue_enqueue(ptrCar car, ptrPQueue pqueue) {
	pthread_mutex_lock(&PQmutex);
	int i;

	if (PQueue_isFull(pqueue)) {
		/* raddoppio la dimensione del vettore */
		ptrCar * newHeap = new_vector(ptrCar, pqueue->capacity*2+1);
		for (i = 0; i <= pqueue->size; i++) {
			newHeap[i] = pqueue->carHeap[i];
		}
		delete(pqueue->carHeap);
		pqueue->carHeap = newHeap;
		pqueue->capacity *= 2;
	}

	pqueue->size++;
	if (pqueue->size == 1) {
		pqueue->carHeap[1] = car;
	} else {
		for (i = pqueue->size;(i != 1) && (Car_getBautArrivalTime(pqueue->carHeap[i / 2])
				> Car_getBautArrivalTime(car)); i /= 2)
			pqueue->carHeap[i] = pqueue->carHeap[i / 2];
		pqueue->carHeap[i] = car;
	}
	pthread_mutex_unlock(&PQmutex);
}


ptrCar PQueue_dequeue(ptrPQueue pqueue) {
	pthread_mutex_lock(&PQmutex);
	int i, minChild;
	ptrCar minElement, lastElement;

	if (PQueue_isEmpty(pqueue)) {
		minElement = pqueue->carHeap[0];
	} else {

		minElement = pqueue->carHeap[1];
		lastElement = pqueue->carHeap[pqueue->size];
		pqueue->size--;

		for (i = 1; i * 2 <= pqueue->size; i = minChild) {

			minChild = i * 2;
			/* scegliamo il minore tra il figlio destro e il figlio sinistro  */
			if (minChild != pqueue->size && Car_getBautArrivalTime(
					pqueue->carHeap[minChild + 1]) < Car_getBautArrivalTime(
					pqueue->carHeap[minChild]))
				minChild++;

			if (Car_getBautArrivalTime(lastElement) > Car_getBautArrivalTime(
					pqueue->carHeap[minChild]))
				pqueue->carHeap[i] = pqueue->carHeap[minChild];
			else {
				break;
			}
		}

		pqueue->carHeap[i] = lastElement;

		if (PQueue_isEmptyEnough(pqueue)) {
			/* dimezza se size è oppurtuna */
			ptrCar * newHeap = new_vector(ptrCar, pqueue->capacity/2);
			for (i = 0; i <= pqueue->size; i++) {
				newHeap[i] = pqueue->carHeap[i];
			}
			delete(pqueue->carHeap);
			pqueue->carHeap = newHeap;
			pqueue->capacity /= 2;
		}
	}
	pthread_mutex_unlock(&PQmutex);
	return minElement;
}

ptrCar PQueue_top(ptrPQueue pqueue) {
	return pqueue->carHeap[1];
}

#ifdef DEBUG
void PQueue_printf(ptrPQueue pqueue) {
	/* BLA, BLA, BLA */
}
#endif /* DEBUG */

static void PQueue_deinit(ptrPQueue pqueue) {
	while (!PQueue_isEmpty(pqueue)) {
		ptrCar car = PQueue_dequeue(pqueue);
		Car_destroy(car);
	}
	pthread_mutex_destroy(&PQmutex);
	delete(pqueue->carHeap);
}


void PQueue_destroy(ptrPQueue pqueue) {
	if (pqueue != NULL) {
		PQueue_deinit(pqueue);
		delete(pqueue);
	}
}
